【题解】[JSOI2004]平衡点 / 吊打XXX

发表于 | 分类于 | 误人子弟 个
字数统计: 904 | 阅读时长 ≈ 4

题目描述

如图：有 n 个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中 X 处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。

问绳结 X 最终平衡于何处。

注意：桌面上的洞都比绳结 X 小得多，所以即使某个重物特别重，绳结 X 也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。

CWaxdf.jpg

输入输出格式

输入格式：

文件的第一行为一个正整数 n（ 1 ≤ n ≤ 1000 ），表示重物和洞的数目。接下来的 n 行，每行是3个整数：Xi . Yi . Wi，分别表示第 i 个洞的坐标以及第 i 个重物的重量。( -10000 ≤ x , y ≤ 10000, 0 < w ≤ 1000 )

输出格式：

你的程序必须输出两个浮点数（保留小数点后三位），分别表示处于最终平衡状态时绳结 X 的横坐标和纵坐标。两个数以一个空格隔开。

输入输出样例

输入样例#1：

3
0 0 1
0 2 1
1 1 1

输出样例#1：

0.577 1.000

思路

这道物理题的正解才不是退火！！！
但是呢，退火是一种玄学的算法，也没有什么模板之说，这道题因其特殊性被很多人当作是退火的入门题。

退火算法的思路其实并不难，就是模拟物理的退火过程，包括：

  1. 加温过程
  2. 等温过程
  3. 冷却过程

设个初始温度变量 t 作为随机取值范围，t 的值随着步骤的进行逐渐减小，从局部最优解着手，在 t 的范围内进行随机取点，若此点更优，则从原点跳到此点，若原点更优，则以一定几率跳到此点（为了跳出局部最优），模拟退火成功率的大小关键在于参数的选取，这需要大量的经验积累（蒟蒻我显然毫无经验）。

代码

若是发现本代码成功率较低（总是 WA 掉），那是血统问题，你可以多进行几次退火（注意 BZOJ 可能会 T 掉）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <algorithm>
#include <cmath>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
typedef long long ll;
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch>'9' or ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' and ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct Node{
    int x,y,w;
}node[10050];
int n;
inline double sum(double x,double y){
    double ans=0;
    rep(i,1,n){
        double de_x=x-node[i].x;
        double de_y=y-node[i].y;
        ans+=(sqrt(de_x*de_x+de_y*de_y))*node[i].w;
    }
    return ans;
}
double ansx,ansy;
double ans=1e18+50;
const double delta=0.993;
inline void SA(){
    double x=ansx,y=ansy,t=192600;
    while(t>1e-14){
        double tox=ansx+(rand()*2-RAND_MAX)*t;
        double toy=ansy+(rand()*2-RAND_MAX)*t;
        double del=sum(tox,toy)-ans;
        if(del<0){
            x=tox;
            y=toy;
            ansx=x;
            ansy=y;
            ans=sum(tox,toy);
        }
        else if(exp(-del/t)*RAND_MAX>rand()){
            x=ansx;
            y=ansy;
        }
        t*=delta;
    }
}
int main(){
    n=read();
    rep(i,1,n){
        node[i].x=read();
        node[i].y=read();
        node[i].w=read();
    }
    SA();
    printf("%.3lf %.3lf\n",ansx,ansy);

    return 0;
}

题目来源

洛谷 P1337 [JSOI2004]平衡点 / 吊打XXX（题目描述清楚）
BZOJ 3680 吊打XXX（数据较强）

0%